package jp.ac.nii.icpc2010.players;

import java.awt.Point;
import java.util.Vector;

import jp.ac.nii.icpc2010.playfield.FieldDirection;
import jp.ac.nii.icpc2010.playfield.IPlayField;

// Player that moves to the point from which the longest hilbert curve can be drawn.
public class HilbertCurvePlayer extends AbstractPlayer {

	private int curIdx;
	private int curLen;
	private Point curPoint;

	private Point curves[][];

	public HilbertCurvePlayer(int id, IPlayField playField) {
		super(id, playField);

		this.curIdx = 0;
		this.curLen = 0;
		this.curPoint = new Point(getX(), getY());

		int width = Math.max(playField.getWidth(), playField.getHeight());
		int bit;
		for(bit = 0; (1 << bit) < width; bit++){}
		Point[] curve = getHilbertCurve(bit);
		//System.err.println(getClass() + " " + bit + " " + curve.length);
		//for(int i = 0; i < curve.length; i++){
		//	System.err.println(getClass() + " (" + curve[i].x + "," + curve[i].y + ")");
		//}

		curves = new Point[8][curve.length];
		if(curve[0].x == 1){
			for(int i = 0; i < curve.length; i++){
				int x = curve[i].x;
				int y = curve[i].y;
				// to right
				curves[0][i] = new Point(x, y);
				curves[4][i] = new Point(x, -y);
				// to left
				curves[1][i] = new Point(-x, y);
				curves[5][i] = new Point(-x, -y);
				// to down
				curves[2][i] = new Point(y, x);
				curves[6][i] = new Point(-y, x);
				// to up
				curves[3][i] = new Point(y, -x);
				curves[7][i] = new Point(-y, -x);
			}
		}else{
			for(int i = 0; i < curve.length; i++){
				int x = curve[i].x;
				int y = curve[i].y;
				// to right
				curves[0][i] = new Point(y, x);
				curves[4][i] = new Point(y, -x);
				// to left
				curves[1][i] = new Point(-y, x);
				curves[5][i] = new Point(-y, -x);
				// to down
				curves[2][i] = new Point(x, y);
				curves[6][i] = new Point(-x, y);
				// to up
				curves[3][i] = new Point(x, -y);
				curves[7][i] = new Point(-x, -y);
			}
		}
	}

	private enum Dir{
		UP, DOWN, RIGHT, LEFT;

		public Dir plus(){
			switch(this){
			case UP:
				return LEFT;
			case LEFT:
				return DOWN;
			case DOWN:
				return RIGHT;
			case RIGHT:
				return UP;
			default:
				return null;
			}
		}
		public Dir minus(){
			switch(this){
			case UP:
				return RIGHT;
			case RIGHT:
				return DOWN;
			case DOWN:
				return LEFT;
			case LEFT:
				return UP;
			default:
				return null;
			}
		}
		public Point step(Point p){
			switch(this){
			case UP:
				return new Point(p.x, p.y + 1);
			case RIGHT:
				return new Point(p.x + 1, p.y);
			case DOWN:
				return new Point(p.x, p.y - 1);
			case LEFT:
				return new Point(p.x - 1, p.y);
			default:
				return null;
			}
		}
		public static Dir getDir(int x, int y){
			if(x > 0){
				return RIGHT;
			}else if(x < 0){
				return LEFT;
			}else if(y > 0){
				return DOWN;
			}else{
				return UP;
			}
		}
		public FieldDirection convert(){
			switch(this){
			case UP:
				return FieldDirection.Up;
			case DOWN:
				return FieldDirection.Down;
			case RIGHT:
				return FieldDirection.Right;
			case LEFT:
				return FieldDirection.Left;
			default:
				return FieldDirection.Up;
			}
		}
	};

	private static Point[] getHilbertCurve(int bit){
		Vector<Point> curve = new Vector<Point>();
		Point[] point = new Point[]{new Point(0, 0)};
		Dir[] dir = new Dir[]{Dir.RIGHT};
		curve.addAll(hilbertCurveL(point, dir, bit - 1));
		return curve.toArray(new Point[curve.size()]);
	}

	// refer Wikipedia
	private static Vector<Point> hilbertCurveL(Point[] point, Dir[] dir, int depth){
		Vector<Point> curve = new Vector<Point>();

		// L --> +RF−LFL−FR+
		// +
		dir[0] = dir[0].plus();
		// R
		if(depth > 0){
			curve.addAll(hilbertCurveR(point, dir, depth - 1));
		}
		// F
		point[0] = dir[0].step(point[0]);
		curve.add(new Point(point[0]));
		// -
		dir[0] = dir[0].minus();
		// L
		if(depth > 0){
			curve.addAll(hilbertCurveL(point, dir, depth - 1));
		}
		// F
		point[0] = dir[0].step(point[0]);
		curve.add(new Point(point[0]));
		// L
		if(depth > 0){
			curve.addAll(hilbertCurveL(point, dir, depth - 1));
		}
		// -
		dir[0] = dir[0].minus();
		// F
		point[0] = dir[0].step(point[0]);
		curve.add(new Point(point[0]));
		// R
		if(depth > 0){
			curve.addAll(hilbertCurveR(point, dir, depth - 1));
		}
		// +
		dir[0] = dir[0].plus();

		return curve;
	}
	private static Vector<Point> hilbertCurveR(Point[] point, Dir[] dir, int depth){
		Vector<Point> curve = new Vector<Point>();

		// R --> -LF+RFR+FL-
		// -
		dir[0] = dir[0].minus();
		// L
		if(depth > 0){
			curve.addAll(hilbertCurveL(point, dir, depth - 1));
		}
		// F
		point[0] = dir[0].step(point[0]);
		curve.add(new Point(point[0]));
		// +
		dir[0] = dir[0].plus();
		// R
		if(depth > 0){
			curve.addAll(hilbertCurveR(point, dir, depth - 1));
		}
		// F
		point[0] = dir[0].step(point[0]);
		curve.add(new Point(point[0]));
		// R
		if(depth > 0){
			curve.addAll(hilbertCurveR(point, dir, depth - 1));
		}
		// +
		dir[0] = dir[0].plus();
		// F
		point[0] = dir[0].step(point[0]);
		curve.add(new Point(point[0]));
		// L
		if(depth > 0){
			curve.addAll(hilbertCurveL(point, dir, depth - 1));
		}
		// -
		dir[0] = dir[0].minus();

		return curve;
	}

	@Override
	public FieldDirection getInput() {

		int width = playField.getWidth();
		int height = playField.getHeight();

		boolean alive = true;
		int remLen = 0;
		for(int i = this.curLen; alive && i < this.curves[this.curIdx].length; i++){
			int x = (this.curPoint.x + this.curves[this.curIdx][i].x + 2 * width) % width;
			int y = (this.curPoint.y + this.curves[this.curIdx][i].y + 2 * height) % height;
			int object = getObjectAt(x, y);
			//System.err.println("BAKA (" + getX() + "," + getY() + ") (" + x + "," + y + ") " + object + " (" + this.curves[this.curIdx][i].x + "," + this.curves[this.curIdx][i].y + ")");
			switch(object){
			case OBJECT_FREE:
			case OBJECT_COIN:
				remLen++;
				break;
			default:
				alive = false;
			}
		}

		int bestIdx = 0;
		int bestLen = 0;
		int bit;
		for(bit = 0; (1 << bit) <= this.curLen + 1; bit++){}
		//System.err.println("AHO " + (1 << bit) + " " + this.curLen + " " + remLen);
		//if(this.curLen + 1 + remLen < (1 << bit))
		{
			for(int i = 0; i < this.curves.length; i++){
				int len = 0;
				alive = true;
				for(int j = 0; alive && j < this.curves[i].length; j++){
					int x = (getX() + this.curves[i][j].x + 2 * width) % width;
					int y = (getY() + this.curves[i][j].y + 2 * height) % height;
					int object = getObjectAt(x, y);
					switch(object){
					case OBJECT_FREE:
					case OBJECT_COIN:
						len++;
						break;
					default:
						alive = false;
					}
				}

				if(len > bestLen){
					bestLen = len;
					bestIdx = i;				
				}
			}
		}

		if(remLen > 0 && bestLen < remLen + 1){
			// continue drawing current hilbert curve
			//System.err.println("AHO " + (this.curLen + 1));
			int dx = (this.curLen == 0 ? this.curves[this.curIdx][0].x : this.curves[this.curIdx][this.curLen].x - this.curves[this.curIdx][this.curLen - 1].x);
			int dy = (this.curLen == 0 ? this.curves[this.curIdx][0].y : this.curves[this.curIdx][this.curLen].y - this.curves[this.curIdx][this.curLen - 1].y);
			this.curLen++;
			return Dir.getDir(dx, dy).convert();
		}else{
			this.curIdx = bestIdx;
			this.curLen = 1;
			this.curPoint = new Point(getX(), getY());

			switch(this.curIdx % 4){
			case 0:
				return FieldDirection.Right;
			case 1:
				return FieldDirection.Left;
			case 2:
				return FieldDirection.Down;
			case 3:
				return FieldDirection.Up;
			default:
				return FieldDirection.Up;
			}
		}
	}

}
